I. Field of the Invention
The present invention relates to both convolutional decoding and to turbo decoding for communications applications and in particular to mobile, point-to-point and satellite communication networks, CDMA (Code Division Multiple Access) and OFDMA (Orthogonal Frequency Division Multiple Access) cellular telephone and wireless data communications with data rates to multiple T1 (1.544 Mbps) and higher (>100 Mbps), and to optical WDMA (Wavelength Division Multiple Access) links with data rates to >100 GBps (Gega bit per second) and higher ranges. More specifically the present invention relates to novel a-posteriori probabilities and decisioning metric paradigms and architectures which reduce the number of arithmetic multiply operations and thereby reduce the computational complexity, improve iterative convergence thereby reducing complexity, improve bit error rate (BER) performance, and provide new metric processing algorithms to support the various decoding algorithms.
II. Description of the Related Art
Current art is represented by the recent IEEE publication in reference [1] which summarizes the theoretical and applications work on turbo codes, books on turbo codes in references [2], [3], [4], [5], [6], [7], [8] and the reference text on the theoretical foundations of probability and decisioning metrics [9]. In addition there are the fundamental patents on turbo decoding.
Maximum likelihood ML decisioning metrics DM are currently used in turbo and convolutional decoding wherein DM is the natural logarithm of the ML probability which is the conditional Gaussian probability of the observed communications channel output symbol y assuming that the transmitted symbol is x. This defines the decisioning metric DM in equations (1) where ln is the natural logarithm and log is the logarithm. Reference to log is understood to mean the natural logarithm since it is always
(1) Decisioning Metric DM                1 mL probability p(y|x) is the Gaussian conditional probabilityp(y|x)=exp(−|y−x|2/2σ2)/(2π)1/2σ        2 Log of the MLln [p(y|x)]=−|y−x|2/2σ2−ln [(2π)1/2σ]        3 Decisioning metric DM is the logarithm of the ML probability with the additive constant term removedDM(y,x)=−|y−x|2/2σ2                     wherein the constant ½σ2 scales the DM relative to the noise floor 2σ2 of the symbol detectorused in turbo decoding and in convolutional decoding. Step 1 is the definition of the zero-mean conditional Gaussian probability density function. Step 2 is the log. Step 3 is the decisioning metric DM that measures the distance between y and x, where σ is the one sigma value of the inphase and the quadrature noise. This DM metric is used in the convolutional decoding algorithm, and in the turbo decoding algorithm when combined with the a-priori probability of the correct decoding bit. The DM metric is a ML distance metric and the functional form is determined by the zero-mean Gaussian assumption for the link and receiver processing noise.                        
Maximum a-posteriori probability MAP turbo decoding starts with a sequence of observed channel output symbols {y(k), k=1, 2, . . . , N} of the receiver where k is the running index over the N transmitted symbols.
FIG. 1 is a representative turbo encoder block diagram for a parallel architecture. Input 1 to the encoder are the user data bits {d(k)} for k=1, 2, . . . , N. The encoder for a turbo code uses a recursive systematic code RSC which means the first codeword bit 2 is the user data bit called systematic bit, or bits, which are uncoded. These user data bits {d(k)} are also handed over to the first RSC encoder 3 called #1 encoder, and after interleaving 4 are also handed over to the second RSC encoder 5 called #2 encoder. User data bits and the encoder output bits are punctured 6 to obtain the correct code rate and then multiplexed into a continuous output bit stream 7 of codewords {c(k)} for each of the codeword clocks k=1, 2, . . . , N. Each codeword c(k) is a set of bits consisting of the systematic bits, #1 encoder output bits, and #2 encoder output bits.
FIG. 2 is a representative transmitter block diagram for implementation of both the turbo encoder in FIG. 1 and the convolutional encoder in FIG. 7. Signal processing starts with the input stream {d(k)} of user data bits 8 to the convolutional/turbo encoder 9. Output 10 of the convolutional/turbo encoder in FIG. 1 are the stream of codewords {c(k)} handed over to the frame processor. Frame processor 11 accepts these codewords and performs error detecting coding such as a CRC (cyclic redundant code) and frame formatting, and passes the outputs to the symbol encoder 12 which encodes the data onto amplitude and phase with possible frequency and time assignments and whose outputs are the transmitter symbols {x(k)} corresponding to the codewords of the convolutional/turbo encoder output as well as the other symbols for the frame data including the CRC. Framing can be done before and/or after the turbo encoding. Transmitter symbols {x(k)} are modulated 13 into a waveform. Modulator output signals for multiple channels are multiple-access processed and combined 14 for handover 14 as a stream of complex baseband digital signal samples {z(ti)} where ti is a time index, to the digital-to-analog conversion processing 15 which converts the complex baseband input signal from the multiple access processing into a single sideband SSB upconverted real signal v(t) 15 at an intermediate frequency IF where {z(ti)} is the stream of complex baseband signal input samples at the digital times {ti} to the digital-to-analog conversion. The digital-to-analog processing also includes beam forming calculations for both digital and analog beam-forming antennas. Multiple access examples in 14 are time division multiple access TDMA, frequency division FDMA, code division CDMA, space division SDMA, frequency hop multiple access FHMA, and all combinations of these and others not mentioned but inferred from this representative list.
For multiple beam antennas 16 in FIG. 2 the beam coefficients for each beam element for each complex digital sample are processed 15 and the individual digital streams are handed off to the corresponding antenna elements where they are SSB upconverted to an IF and processed by the analog front end 16 at each element and the array of elements form the beams and within each beam the transmitted signal is similar to the real RF signal v(t) in 17 for a single beam. For single beams the analog front end 16 upconverts and amplifies this IF signal and transmits it as the real RF signal v(t) 17. This real waveform v(t) 17 is at the RF carrier frequency f0 and is the real part of the complex envelope of the baseband waveform z(t) multiplied by the RF carrier with the phase angle φ which accounts for the phase change from the baseband signal to the transmitted signal.
MAP (maximum a-posteriori probability) joint probability used in the MAP turbo decoding algorithm is defined in equations (2) which are taken from references [1],[2]. Definition 1 introduces common terminology in
(2) MAP Joint Probability for Turbo Decoding                1 Definitions        
                                          S            ⁡                          (              k              )                                =                    ⁢                                    Decoder  trellis  state  at  clock                          ⁢            k                                                        =                    ⁢                                    Decoder  shift  register  state  at  clock                        ⁢                                                  ⁢            k                                                            k          =                      Index  of  received  codewords                                                        =                      trellis  decoder  states                                                        =                      decoding  clock                                          s      ′        ,          s      =                        Values  of                  ⁢                  S          ⁡                      (                          k              -              1                        )                                ,                  ⁢                  S        ⁡                  (          k          )                    ⁢                          ⁢              respectively                                          y          =                    ⁢                      Set  of  observed  channel  output  symbols                                                        =                    ⁢                      {                                          y                ⁡                                  (                  k                  )                                            ,                              k                =                1                            ,              2              ,              …              ⁢                                                          ,              N                        }                                                                        R            ⁢                                                  ⁢            S            ⁢                                                  ⁢            C                    =                    ⁢                      Recursive  systematic  code                                                        =                    ⁢                                    Systematic code                          ⁢            S            ⁢                                                  ⁢            C            ⁢                            with  feedback  which  is  a                                                                              ⁢                      requirement  for  turbo  decoding                                                                  Parallel encoding=Encoding configuration for turbo decoding which transmits the symbols using a parallel architecture, which is the assumed architecture for this invention disclosure            y(k)=Output symbols for codeword/clock k            {y(j<k)}=Output symbols for clocks j=1, 2, . . . , k−1            {y(j>k)}=Output symbols for clocks j=k+1, 2, . . . , N                        2 Decoding states and observations                    Observations are the set {y(k), k=1, 2, . . . , N)                        
                                    Subsets y(j<k), y(k), y(j>k) of y are of interest                        
                                    Decoder trellis states of interest are s′,s                        
                3 MAP joint probability                    The joint probability of interest for MAP isp(s′,s,y)=p(s′,s,y(j<k),y(k),y(j>k))turbo decoding literature. In 2 the decoding states s′,s are defined at clocks k−1,k and the observations are defined over the j=1, 2, . . . , k−1 as y(j<k), over j=k+1, . . . , N as y(j>k), and at k as y(k). In 3 the MAP joint probability is defined as a function of these decoder states and observations.                        
Recursive equation for the MAP joint probability is derived in equations (3) by reformulating the joint probability equation in 3 in equations (2) as a function of the recursive state estimators α,β and the state transition probability γ. Step 1 is the application of Bayes rule to partition the joint probability. Step 2 takes advantage of the assumption that the
(3) Recursive Formulation of MAP Joint Probability                1 Bayes theorem or rule p(a,b)=p(a|b)p(b) can be used to rewrite the MAP joint probability in 3 in equation (2)        
                              p          ⁡                      (                                          s                ′                            ,              s              ,              y                        )                          =                ⁢                  p          (                                    s              ′                        ,            s            ,                          y              ⁡                              (                                  j                  <                  k                                )                                      ,                          y              ⁡                              (                k                )                                      ,                          y              ⁡                              (                                  j                  >                  k                                )                                                                            =                ⁢                              p            ⁡                          (                                                                    y                    ⁡                                          (                                              j                        >                        k                                            )                                                        |                                      s                    ′                                                  ,                s                ,                                  y                  ⁡                                      (                                          j                      <                      k                                        )                                                  ,                                  y                  ⁡                                      (                    k                    )                                                              )                                *                                                ⁢                  p          ⁡                      (                                          s                ′                            ,              s              ,                              y                ⁡                                  (                                      j                    <                    k                                    )                                            ,                              y                ⁡                                  (                  k                  )                                                      )                          )                                                where “*” is a multiply operation                        2 Assuming the channel is memorylessp(s′,s,y)=p(y(j>k)|s)p(s′,s,y(j<k),y(k))        3 Re-applying Bayes rule and the assumption that the channel is memorylessp(s′,s,y)=p(y(j>k)|s)p(s,y(k)|s′)p(s′,y(j<k))        4 This equation can be rewritten as a function of the recursive estimators and state transition probabilityp(s,s′,y)=βk(s)γk(s,s′)αk−1(s′)                    where by definition                            βk(s)=p(y(j>k)|s)                γk(s,s′)=p(s,y(k)|s′)                αk−1(s′)=p(s′,y(j<k))channel is memoryless to simplify the partitioning in step 1. Step 3 re-applies the Bayes rule and the memoryless assumption to re-partition the equation and simplify it to the final form used in the MAP algorithm. Step 4 transforms the joint probability in step 3 derived as a product of three probabilities, into the equivalent product of the two estimators αk−1(s′),βk(s) and the state transition probability γk(s,s′) for the MAP algorithm.                                                
Forward recursive equation for the state estimator αk(s) is derived in equations (4) as a forward recursion which is a function of γk(s,s′) and the previous estimate αk−1(s′). Step 1 starts with the definition of αk(s) which is derived from the equation for αk−1(s′) in 4 in equations (3). Step 2 introduces the state s′ by observing that the probability summed over all values of s′ is equal to the probability with s′ excluded. Step 3 applies Bayes rule to partition the probabilities. In step 4 the assumption that the channel is memoryless enables the equation to be simplified to the form used
(4) Forward Recursive Equation for αk(s)                1 Definition of αk−1(s′) in 4 in equations (3) givesαk(s)=p(s,y(j<k),y(k))        2 This probability can be written as the sum of joint probabilities over all possible states of s′αk(s)=Σall s′p(s,s′,y(j<k),y(k))        3 Applying Bayes ruleαk(s)=Σall s′p(s,s′,y(k)|s′,y(j<k))p(s′,y(j<k))        4 Applying the channel memoryless assumptionαk(s)=Σall s′p(s,y(k)|s′)p(s′,y(j<k))        5 Substituting the definitions of γk(s,s′) and αk−1(s′) from 4 in equations (3)αk(s)=Σall s′γk(s,s′)αk−1(s′)in the MAP algorithm. In step 5, substitution of γk(s,s′) and αk−1(s′) from 4 in equations (3) gives the final form for the recursive equation for αk(s).        
Backward recursive equation for the state estimator βk−1(s′) is derived as a backward recursion in equations (5) as a function of the γk(s,s′) and the previous estimate βk(s), following the steps in equations (4). Step 1 derives βk−1(s′) from the equation for βk(s) in 4 in equations (3). Step 2 follows steps 2, 3, 4 in the derivation of αk(s) in equations (4).
(5) Backward Recursion Equation for βk−1(s′)                1 The definition for βk(s) from 4 in equations (3)βk−1(s′)=p(y(j>k−1)|s′)        2 Following steps similar to steps 2, 3, 4 in equations (4)βk−1(s′)=Σall sp(y(j>k)|s)p(s,y(k)|s′)        3 Substituting the definitions of γk(s,s′) and βk(s) from 4 in equations (3)βk−1(s′)=Σall sβk(s)γk(s,s′)In step 3, substitution γk(s,s′) and βk(s) from 4 in equations (3) gives the final form for the recursive equation for βk−1(s′).        
State transition probability γk(s,s′) and the log, γk(s,s′) of γk(s,s′) are derived in equations (6). The γk(s,s′) is the probability of
(6) State Transition Probabilities γk(s,s′),γk(s,s′)                1 From the definition of γk(s,s′) from 4 in equations (3) and Bayes rule        
                                          γ            k                    ⁡                      (                          s              ,                              s                ′                                      )                          =                  p          ⁡                      (                          s              ,                                                y                  ⁡                                      (                    k                    )                                                  |                                  s                  ′                                                      )                                                  =                              p            ⁡                          (                                                                    y                    ⁡                                          (                      k                      )                                                        |                  s                                ,                                  s                  ′                                            )                                ⁢                      p            ⁡                          (                              s                |                                  s                  ′                                            )                                                          2 Define        
                                          d            ⁡                          (              k              )                                =                    ⁢                      input  bit  necessary  to  cause  the  transistion  from  state                                                                  ⁢                                    S              ⁡                              (                                  k                  -                  1                                )                                      =                                                            s                  ′                                ⁢                                                                  ⁢                                  to                                ⁢                                                                  ⁢                                  S                  ⁡                                      (                    k                    )                                                              =              s                                                      p      ⁡              (                  d          ⁡                      (            k            )                          )              =                  a-priori  probability  of              ⁢              d        ⁡                  (          k          )                                                              x            ⁡                          (              k              )                                =                    ⁢                      transmitted  codeword  symbols  defines  the  transition                                                                  ⁢                                                    from                            ⁢                                                          ⁢                              S                ⁡                                  (                                      k                    -                    1                                    )                                                      =                                                            s                  ′                                ⁢                                                                  ⁢                to                ⁢                                                                  ⁢                                  S                  ⁡                                      (                    k                    )                                                              =              s                                                                    =                    ⁢                                    {                              x                ⁡                                  (                                      k                    ,                    b                                    )                                            )                        ⁢                                                  ⁢                          where                          ⁢            b            ⁢                            refers  to  the  codeword  bit                                                                                    y            ⁡                          (              k              )                                =                    ⁢                                    received  codeword  symbols  for  codeword/clock                          ⁢            k                                                                  ⁢                                    {                              y                ⁡                                  (                                      k                    ,                    b                                    )                                            }                        ⁢                                                  ⁢                          where                          ⁢            b            ⁢                            refers  to  the  codeword  bit                                                          3 With these definitions and the memoryless assumption, the γk(s,s′) equation in 1 becomes        
                                          γ            k                    ⁡                      (                          s              ,                              s                ′                                      )                          =                              p            ⁡                          (                                                                    y                    ⁡                                          (                      k                      )                                                        |                  s                                ,                                  s                  ′                                            )                                ⁢                      p            ⁡                          (                              d                ⁡                                  (                  k                  )                                            )                                                              =                              p            ⁡                          (                                                y                  ⁡                                      (                    k                    )                                                  |                                  x                  ⁡                                      (                    k                    )                                                              )                                ⁢                      p            ⁡                          (                              d                ⁡                                  (                  k                  )                                            )                                                              =                              ∏            b                    ⁢                                    p              ⁡                              (                                                      y                    ⁡                                          (                                              k                        ,                        b                                            )                                                        |                                      x                    ⁡                                          (                                              k                        ,                        b                                            )                                                                      )                                      ⁢                          p              ⁡                              (                                  d                  ⁡                                      (                    k                    )                                                  )                                                                        4 Assume the channel is Gaussian and the symbols are BPSKγk(s,s′)=Πbexp(−|y(k,b)−x(k,b)|2/2σ2)(2π)1/2σ*p(d(k))        5 The DM from 3 in equations (1) can be rewritten        
                              D          ⁢                                          ⁢                      M            ⁡                          (                              s                |                                  s                  ′                                            )                                      =                              ∑            b                    ⁢                      DM            ⁡                          (                                                y                  ⁡                                      (                                          k                      ,                      b                                        )                                                  ,                                  x                  ⁡                                      (                                          k                      ,                      b                                        )                                                              )                                                              =                              ∑            b                    ⁢                                                    -                                                                                                                        y                        ⁡                                                  (                                                      k                            ,                            b                                                    )                                                                    -                                              x                        ⁡                                                  (                                                      k                            ,                            b                                                    )                                                                                                                          2                                            /              2                        ⁢                                                  ⁢                          σ              2                                                          6 Log equation for γk(s,s′) takes the log, uses DM, and deletes the additive constantγk(s,s′)=DM(s|s′)+p(d(k))                    wherein p(d(k))=log(p(d(k)))the decoder trellis state S(k−1)=s′ transitioning to the next state S(k)=s symbolically written as s′→s. Step 1 applies Bayes rule to the definition of γk(s,s′) in 4 in equations (3). Step 2 are definitions. Step 3 uses these definitions to transform the γk(s,s′) into the product of the conditional probabilities p(y(k)|x(k)) of the received codeword symbols {y(k)} given the transmitted codeword symbols {x(k)}, and the a-priori probability p(d(k)) causing this transition. The p(y(k)|x(k)) is the product over the bits b=1, 2, . . . for the #1 or #2 encoders in FIG. 1 depending on which is being addressed, of the probabilities for each bit p(y(x,b)|x(k,b)).                        
Step 4 introduces the standard turbo code assumption that the channel is Gaussian and uses BPSK (Binary phase shift keying) symbols which means d(k)=+/−1 when interpreted as a BPSK symbol, and σ is the one sigma Gaussian inphase and quadrature noise. Step 5 observes that the DM metric is a function of the states s,s′ which is equal to the sum of the DM metrics over the bits {b} of the codeword corresponding to the transition from S(k−1)=s′ to S(k)=s. In step 6 the equation for the log, γk(s,s′), of γk(s,s′) as a function of the DM metric and the log, p(d(k)), of p(d(k)) is used in turbo decoding algorithms, and in convolutional decoding algorithms when p(d(k)) is deleted.
Log equations for αk(s), βk−1(s′) are derived in equations (7) from equations (4),(5) respectively for αk(s), βk−1(s′) using the definition of γk(s,s′) in 6 in equations (6). Step 1 gives the log equation for αk(s) by taking the
(7) Log Equations for αk(s), βk−1(s′)                1 Log, αk(s), of αk(s)αk(s)=ln [Σall s′exp(αk−1(s′)+DM(s s′)+p(d(k))]        2 Log, βk−1(s′), of βk−1(s′)βk−1(s′)=ln [Σall sexp(βk(s)+DM(s|s′)+p(d(k))]log of the αk(s) equation in 5 in equations (4) and using the definition of γk(s,s′) in 6 in equations (6). Step 2 takes the log of the equation for βk−1(s′) in 3 in equations (5) to derive the log equation for βk−1(s′) and uses the same definition for γk(s,s′).        
MAP equations for the log likelihood ratio L(d(k)|y)) are derived in equations (8). Step 1 is the definition from references [1],[2]. Step 2 uses the Bayes rule P(a,b)=P(a|b)P(b) with the p(y) cancelled in the division. Step 3 replaces p(d(k)) with the
(8) MAP Equations                1 DefinitionL(d(k))|y)=ln [p(d(k)=+1|y)]−ln [p(d(k)=−1|y)]        2 Bayes rule allows this to be rewrittenL(d(k))|y)=ln [p(d(k)=+1,y)]−ln [p(d(k)=−1,y)]        3 Probability of p(d(k)) is the sum of the probabilities that the state S(k−1)=s′ transitions to S(k)=s for the assumed values d(k)=+1 and d(k)=−1L(d(k))|y)=ln [Σ(s,s′|d(k)=+1)p(s,s′,y)]−ln [Σ(s,s′|d(k)=−1)p(s,s′,y)]        4 MAP equation is obtained by substituting the αk−1(s′), βk(s), γk(s,s′) into 3        
                                                        L              ⁡                              (                                  d                  ⁡                                      (                    k                    )                                                  )                                      |            y                    )                =                ⁢                              ln            [                                          ∑                                  (                                      s                    ,                                                                                            s                          ′                                                |                                                  d                          ⁡                                                      (                            k                            )                                                                                              =                                              +                        1                                                                              )                                            ⁢                              p                ⁡                                  (                                      s                    ,                                          s                      ′                                        ,                    y                                    )                                                      ]                    -                                                ⁢                  ln          [                                    ∑                              (                                  s                  ,                                                                                    s                        ′                                            |                                              d                        ⁡                                                  (                          k                          )                                                                                      =                                          -                      1                                                                      )                                      ⁢                          p              ⁡                              (                                  s                  ,                                      s                    ′                                    ,                  y                                )                                              ]                                        =                ⁢                  ln          [                                    ∑                              (                                  s                  ,                                                                                    s                        ′                                            |                                              d                        ⁡                                                  (                          k                          )                                                                                      =                                          +                      1                                                                      )                                      ⁢                          exp              (                                                                                          α                      _                                                              k                      -                      1                                                        ⁡                                      (                                          s                      ′                                        )                                                  +                                  DM                  ⁡                                      (                                          s                      |                                              s                        ′                                                              )                                                  +                                                                                    ⁢                                            p              _                        ⁡                          (                              d                ⁡                                  (                  k                  )                                            )                                +                                                                      β                  _                                k                            ⁡                              (                s                )                                      ⁢                                         )                        ⁢                                         ]                                -                                                ⁢                  ln          [                                    ∑                              (                                  s                  ,                                                                                    s                        ′                                            |                                              d                        ⁡                                                  (                          k                          )                                                                                      =                                          -                      1                                                                      )                                      ⁢                          exp              (                                                                                          α                      _                                                              k                      -                      1                                                        ⁡                                      (                                          s                      ′                                        )                                                  +                                  DM                  ⁡                                      (                                          s                      |                                              s                        ′                                                              )                                                  +                                                                                    ⁢                                            p              _                        ⁡                          (                              d                ⁡                                  (                  k                  )                                            )                                +                                                                      β                  _                                k                            ⁡                              (                s                )                                      ⁢                                         )                        ⁢                                                                          ]                                                                        5 Decide        
                              d          ⁡                      (            k            )                          =                                            +              1                        ⁢                                                  ⁢                          when                           ⁢                          L              ⁡                              (                                                      d                    ⁡                                          (                      k                      )                                                        |                  y                                )                                              ≥          0                                        =                                            -              1                        ⁢                                                  ⁢                          when                           ⁢                          L              ⁡                              (                                                      d                    ⁡                                          (                      k                      )                                                        |                  y                                )                                              <          0                    equivalent sum of the probabilities that the transition from S(k−1)=s′ to S(k)=s occurs for d(k)=+1 and for d(k)=−1. Step 4 substitutes the log of the recursive estimators αk−1(s′),βk(s), from 1,2 in equations (7) and the state transition probability γk(s,s′) from 6 in equations (6). In step 5 the hard decisioning rule is d(k)=+/−1 iff L(d(k)|y)≧/<0 and the soft decisioning metric is the value of L(d(k)|y).
MAP turbo decoding iterative algorithm is defined in FIG. 3 and in equations (9) for a parallel architecture using the MAP a-posteriori equation in equations (8) with BPSK (Binary Phase Shift Keying) modulation. This basic algorithm is used to illustrate how the decisioning metric DM is implemented, and is representative of how the DM metric is used for the more efficient algorithms such as the Log-MAP, Max-Log-MAP, iterative SOVA, and others, for parallel and serial architectures and other variations, and for modulations other than BPSK.
FIG. 3 inputs are the detected soft output symbols 18 from the received channel demodulator which detects and recovers these symbols. This stream of output symbols consists of the outputs {y(k,b=1)} for the systematic bit b=1 which is the uncoded bit, the subset of the output symbols from #1 encoder 3 in FIG. 1, and the remaining output symbols from #2 encoder 5 in FIG. 1. Systematic bits are routed to both #1 decoder 22 and #2 decoder 25. Encoded bits from #1 and #2 encoders are separately routed 19 to #1 and #2 decoders. The detailed decoding in FIG. 3 will be described in parallel with the MAP turbo decoding iterative algorithm in equations (9). In equations (9), step 1 defines the various parameters used in the turbo decoding iterations.
Step 2 starts iteration i=1 in FIG. 3 for #1 decoder 22. Extrinsic information L1e from this decoder 22 in FIG. 3 for i=1 is calculated in step 2 in equations (9) using the soft outputs {y(k,b=1)} 20 of the received channel for the systematic bit b=1 which is the uncoded bit, the subset of the detected output symbols 19 which are from #1 decoder 3 in FIG. 1, and the #1 decoder likelihood ratio output L1 calculated from 4 in equations 8. The a-priori information on p(d(k)) in 4 in equations (8) from #2 decoder 25 is not available so p(d(k))=0 corresponding to p(d(k)=+1)=p(d(k)=−1)=½.
(9) MAP Turbo Decoding Iterative Algorithm                Step 1 Definitions        
                                                                                                                                    L                      m                                        =                                        ⁢                                          {                                              L                        ⁡                                                  (                                                                                    d                              ⁡                                                              (                                k                                )                                                                                      |                            y                                                    )                                                                    )                                                        ,                                      k                    =                    1                                    ,                  2                  ,                                      …                    ⁢                                                                                  .                                                  }                            ⁢                                                          ⁢              for              ⁢                                                          ⁢              m                        =            #1                    ,                      #2            ⁢                                                  ⁢            decoders                                                        =                    ⁢                      a-posteriori  likelihood  ratio                                                                                                      L                me                            =                            ⁢                              {                                                      L                    me                                    ⁢                                      (                                                                  d                        ⁡                                                  (                          k                          )                                                                    |                      y                                        )                                                  )                                      ,                          k              =              1                        ,            2            ,                          …              ⁢                                                          .                                }                                                          =                        ⁢                                                            extrinsic  information  from                                  ⁢                m                            =              #1                                ,                      #2            ⁢                            decoder                                                                    =                    ⁢                                    a-priori  estimates  of                          ⁢                          ln              ⁡                              [                                                      p                    ⁡                                          (                                              d                        =                                                  +                          1                                                                    )                                                        /                                      p                    ⁡                                          (                                              d                        =                                                  -                          1                                                                    )                                                                      ]                                      ⁢                                                  ⁢            which                                                                  ⁢                                    defines                          ⁢                          p              _                        ⁢                            for  the  other  decoder  using  equations                                                                              ⁢                                    (              10              )                        ⁢                            to  solve  for                          ⁢                          p              _                                                          {tilde over (L)}1e=Interleaved L1e         {tilde over (L)}2e,{tilde over (L)}2=De-interleaved L2e, L2         y(k,b=1)=y for uncoded bit b=1                    {tilde over (y)}(k,b=1)=interleaved y for uncoded bit b=1                        Step 2 Iteration i=1 starts the turbo decodingL1e=L1−0−(2/σ2)Re[y(k,b=1)]L2e=L2−{tilde over (L)}1e−(2/σ2)Re[{tilde over (y)}(k,b=1)]                    where Re(o)=Real(o)                        Step 3 For iteration i=2, 3, . . .L1e=L1−{tilde over (L)}2e−(2/σ2)Re[y(k,b=1)]L2e=L2−{tilde over (L)}1e−(2/σ2)Re[{tilde over (y)}(k,b=1)}        Step 4 Decode after last iteration                    Decide {circumflex over (d)}(k)=+1/−1≡1/0 bit value            for {tilde over (L)}2(d(k)|y)≧/<0 for k=1, 2, . . .            where {circumflex over (d)}(k) is the estimate of d(k) from turbo decoding                        
Step 2 next proceeds to #2 decoder 25. A-priori estimates for p(d(k)) are calculated from the extrinsic information from #1 decoder after interleaving 23 in FIG. 3 in order to align the bits with the interleaved bits 4 in FIG. 1 which are encoded by the #2 encoder 5. Calculation of the a-priori p for #1,#2 decoder using the extrinsic information from #2,#1 decoder is given in equations (10) from references [2],[4]. Inputs to the
(10) A-Priori Calculation of p in 4 in Equations 8K=[1+exp({tilde over (L)}me)]p(d(k)=−1)=−ln(K)p(d(k)=+1)={tilde over (L)}me−ln(K)#2 decoder 25 in FIG. 3 are the detected output symbols 19 from the #2 encoder 5 in FIG. 1, the detected symbols for the systematic bits 21 after interleaving 24, and the extrinsic information from #1 decoder 22 after interleaving 23. Calculation of the extrinsic information L2e from #2 decoder is given in step 2 in equations (9).
Step 3 repeats step 2 with the subtraction of the de-interleaved 26 extrinsic information input {tilde over (L)}2e to #1 decoder 22 from #2 decoder 25. This {tilde over (L)}2e is used to calculate the a-priori probabilities p using equations (10) for use in the evaluation of the a-posterior likelihood ratio L1 from decoder #1, and also used in the calculation of the extrinsic information Lie for decoder #1 in step 3 in equations (9).
Step 4 is the calculation of the estimates {{circumflex over (d)}(k)} for the transmitted information {d(k)} in the form of +/−1 used in the iterative algorithm to model the BPSK modulation with values +/−1 for the estimated input signal {{circumflex over (d)}(k)} in 28 with +1 corresponding to the bit value 1 and −1 for the bit value 0. The de-interleaved 27 a-posteriori maximum likelihood ratio {tilde over (L)}2 from #2 decoder in FIG. 3 yields these output bits 28 using the hard decisioning rule that decides 1/0 depending on whether the {tilde over (L)}2 is ≧0 or <0.
Convolutional decoding will be discussed in the disclosure of the new invention.
FIG. 4 is a representative demodulation receiver block diagram for implementation of the turbo decoder in FIG. 3 and the convolutional decoder in FIG. 8, which emphasizes the demodulation processing for both single and multiple channels. The signal processing starts with the user transmitted wavefronts 29 incident at the receiver antenna for the nu users u=1, . . . , nu≦Nc. These wavefronts are combined by addition in the antenna to form the receive Rx signal {circumflex over (v)}(t) at the antenna output 30 where {circumflex over (v)}(t) is an estimate of the transmitted signal v(t) 17 in FIG. 2, that is received with errors in time Δt, frequency Δf, phase Δθ, and with an estimate {circumflex over (z)}(t) of the transmitted complex baseband signal z(t) 14 in FIG. 2. This received signal {circumflex over (v)}(t) is amplified and downconverted by the analog front end 31 and then synchronized and analog-to-digital ADC converted 32. Outputs from the ADC are handed over to the multiple access channel recovery signal processing 33 and the demodulation processing 34 where the waveform is removed to recover the symbols 35. These detected symbols 35 are turbo/convolutional decoded 36 to recover estimates {{circumflex over (d)}(k)} of the received data which are processed by the frame processor 37 to recover estimates 38 of the transmitted user data words. The serial processing for the multiple access channel recovery and the demodulator is combined for several of the multiple access schemes and for the demodulation such as GMSK. As noted in the discussion for FIG. 2, the frame processing can be before and/or after the turbo decoder.
It should be obvious to anyone skilled in the communications art that this example implementation clearly defines the fundamental current turbo and convolutional encoding and decoding signal processing relevant to this invention disclosure and it is obvious that this example is representative of the other possible signal processing approaches.
For cellular applications the transmitter description describes the turbo and convolutional encoding transmission signal processing applicable to this invention for both the hub and user terminals, and the receiver describes the corresponding turbo and convolutional decoding receiving signal processing for the hub and user terminals for applicability to this invention.
For optical communications applications the microwave processing at the front end of both the transmitter and the receiver is replaced by the optical processing which performs the complex modulation for the optical laser transmission in the transmitter and which performs the optical laser receiving function of the microwave processing to recover the complex baseband received signal with the remainder of the signal processing functionally the same as described in FIG. 2 for the turbo and convolutional encoding transmitter and in FIG. 4 for the turbo and convolutional decoding receiver.